﻿package astar {
	import flash.utils.Dictionary;
	import org.flixel.*;

	/**
	 * ...
	 * @author test
	 */
	public class AStar {
		public var open_list:MinHeap;
		public var in_open_list:Dictionary;
		public var closed_list:Array;

		public var tilemap:FlxTilemap
		public var nodes_arry:Array;
		public var path:Array;

		public var _allow_:int;
		public var _denied_:int;
		public var _source_:FlxPoint;
		public var _target_:FlxPoint;
		
		static public var DOWN:uint = 0;
		static public var RIGHT:uint = 1;
		static public var LEFT:uint = 2;
		static public var UP:uint = 3;
		static public var DIR_ARR:Array = [DOWN, RIGHT, LEFT, UP];
		static public var DIR:Array = [[0, 1], [1, 0], [-1, 0], [0, -1]/* , [1, 1], [1, -1], [-1, 1], [-1, -1]*/];
		static public var NULL_NODE:Node = new Node(999999, 999999, 999999);

		public function AStar(_tilemap:FlxTilemap, _allow:int, _denied:int){
			_allow_ = _allow;
			_denied_ = _denied;
			tilemap = _tilemap;
		}
		
		static public function chooseDir(_n1:Node, _n2:Node):uint {
			var _n:Node = new Node(_n1.tid, _n2.x - _n1.x, _n2.y - _n1.y);
			for each(var i:uint in DIR_ARR) {
				if (_n.x == DIR[i][0] && _n.y == DIR[i][1]) {
					return i;
				}
			}
			return 0;
		}

		public function openlist_push(n:Node):void {
			open_list.push(n);
			in_open_list[n] = true;
		}

		public function openlist_pop():Node {
			var n:Node = open_list.pop();
			in_open_list[n] = false;

			return n;
		}

		public function start(_source:FlxPoint, _target:FlxPoint):void {
			reset();
			
			trace(_source.x, _source.y);
			trace(_target.x, _target.y);
			
			_source_ = _source;
			_target_ = _target;
			buildNodes();

			openlist_push(nodes_arry[_source_.x][_source_.y]);

			while (open_list.size != 0 && closed_list[_target_.x][_target_.y] == false){
				var cur_node:Node = openlist_pop();
				closed_list[cur_node.x][cur_node.y] = true;

				for each (var dir:Array in DIR){
					var tx:int = cur_node.x + dir[0];
					var ty:int = cur_node.y + dir[1];

					var n_d:Node = nodes_arry[tx][ty];

					if (judgeRange(tx, ty)){
						if (n_d.tid == _allow_ && closed_list[tx][ty] == false){

							if (in_open_list[n_d] == true){
								if (cur_node.g + 1 < n_d.g){
									cur_node.g++;
									n_d.parent = cur_node;
								}
							} else {
								n_d.g = cur_node.g + 1;
								n_d.parent = cur_node;

								openlist_push(n_d);
							}
						}
					}

				}
			}

			buildPath();
		}

		public function buildPath():void {
			var cn:Node = nodes_arry[_target_.x][_target_.y];
			do {
				path.push(cn);
				cn = cn.parent;
			} while (cn != NULL_NODE);
			//path.push(nodes_arry[_source_.x][_source_.y]); //加入起始點至開頭
			path.reverse();
		}

		public function print_path():void {
			var out:String = new String();
			for each (var n:Node in path){
				out += "(" + n.x + ", " + n.y + ") -> ";
			}
			trace(out);
		}

		public function judgeRange(_x:uint, _y:uint):Boolean {
			return _x >= 0 && _y >= 0 && _x < tilemap.widthInTiles && _y < tilemap.heightInTiles;
		}

		public function buildNodes():void {
			for (var i:uint = 0; i < tilemap.widthInTiles; i++){
				nodes_arry[i] = new Array();
				closed_list[i] = new Array();
				for (var j:uint = 0; j < tilemap.heightInTiles; j++){
					var tid:int = tilemap.getTile(i, j);
					nodes_arry[i][j] = new Node(tid, i, j);
					nodes_arry[i][j].h = H(nodes_arry[i][j]);
					nodes_arry[i][j].parent = NULL_NODE;

					closed_list[i][j] = new Boolean(false);
				}
			}
		}

		public function reset():void {
			path = new Array();
			nodes_arry = new Array();
			open_list = new MinHeap(comp);
			closed_list = new Array();
			in_open_list = new Dictionary();
		}

		public function comp(n1:Node, n2:Node):int {
			F(n1);
			F(n2);
			if (n1.f < n2.f)
				return MinHeap.SMALLER;
			if (n1.f > n2.f)
				return MinHeap.BIGGER;
			return MinHeap.EQUAL
		}

		public function F(node:Node):int {
			return (node.f = node.g + node.h);
		}

		public function H(node:Node):int {
			return Math.abs(node.x - _source_.x) + Math.abs(node.y - _source_.y);
		}
	}

}